#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Solution
{
public:
    int numDistinct(string s, string t)
    {
        vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, -1));
        return ms(s, t, 0, 0, dp);
    }

    int ms(string &s, string &t, int i, int j, vector<vector<int>> &dp)
    {
        if (dp[i][j] != -1)
            return dp[i][j];
        if (j == t.size())
        {
            dp[i][j] = 1;
            return dp[i][j];
        }
        if (i == s.size())
            dp[i][j] = 0;
        else
            dp[i][j] = ms(s, t, i + 1, j, dp);
        if (s[i] == t[j])
            dp[i][j] += ms(s, t, i + 1, j + 1, dp);
        return dp[i][j];
    }
};

int main()
{
    cout << "Code115" << endl;
    Solution s;
    cout << s.numDistinct("rabbbit", "rabit") << endl;
    cout << s.numDistinct("babgbag", "bag") << endl;
    return 0;
}